package com.example.validatestudy.demos.algorithm.sort;

/**
 * @param
 * @version v1
 * @auther WANGZHENFANG004
 * @summary 插入排序
 * @since 2024 07 01 10 23
 */
public class InsertSort {

    /**
     * 耗时时常：插入排序<选择排序<冒泡排序
     * @param args
     */
    public static void main(String[] args){
        int[] arr = {30,40,60,10,20,50};
        arr = insertSort2(arr);
        for(int i=0;i<arr.length;i++){
            System.out.println(arr[i]);
        }
    }

    public static int[] insertSort2(int[] arr){
        int length = arr.length;
        for (int i = 1; i < length; i++) {
            int j = i;
            while (j > 0 && arr[j]<arr[j-1]){
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                j--;
            }
        }
        return arr;
    }



    public static int[] insertSort(int[] arr){
        int n = arr.length-1;
        int i = 0;//记录已排序位置
        while (i<n && arr[i+1]>arr[i]){
            i++;
        }
        for ( ; i < n; i++) {
            int x = arr[i+1];//未排序的数
            int c = 0;//插入位置
            for (int k = i; k >= 0; k--) {
                if(x>arr[k]){
                    c = k+1;
                    break;
                }
            }
            for (int m = i; m >= c; m--) {
                arr[m+1] = arr[m];
            }
            arr[c] = x;
        }
        return arr;
    }



}
